import heapq


class Solution(object):
    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]]
        :rtype: List[List[int]]
        """
        n = len(buildings)
        start = [buildings[i][0] for i in range(n)]
        end = [buildings[i][1] for i in range(n)]
        end.sort()
        left_index = 0
        right_index = 0
        height = []
        out = []
        while left_index < n:
            if start[left_index] <= end[right_index]:
                if not height:
                    out.append([start[left_index], buildings[left_index][2]])
                else:
                    if buildings[left_index][2] > - height[0][0]:
                        if out:
                            if buildings[left_index][0] == out[-1][0]:
                                out[-1][1] = max(out[-1][1], buildings[left_index][2])
                            else:
                                out.append([start[left_index], buildings[left_index][2]])
                        else:
                            out.append([start[left_index], buildings[left_index][2]])
                heapq.heappush(height, [-buildings[left_index][2], buildings[left_index][1]])
                left_index += 1
            else:
                while start[left_index] > end[right_index]:
                    if height:
                        if end[right_index] == height[0][1]:
                            node = heapq.heappop(height)
                            while height and height[0][1] <= node[1]:
                                heapq.heappop(height)
                            if height:
                                if node[0] < height[0][0]:
                                    out.append([node[1], - height[0][0]])
                            else:
                                out.append([node[1], 0])
                    right_index += 1
        while height:
            node = heapq.heappop(height)
            while height and height[0][1] <= node[1]:
                heapq.heappop(height)
            if height:
                if node[0] < height[0][0]:
                    out.append([node[1], - height[0][0]])
            else:
                out.append([node[1], 0])
        return out


data = Solution()
# buildings = [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]
# print(data.getSkyline(buildings))
# buildings = [[0, 2, 3], [2, 5, 3]]
# print(data.getSkyline(buildings))
# buildings = [[0, 4, 2]]
# print(data.getSkyline(buildings))
# buildings = [[1, 2, 1], [1, 2, 2], [1, 2, 3]]
# print(data.getSkyline(buildings))
buildings = [[4, 9, 10], [4, 9, 15], [4, 9, 12], [10, 12, 10], [10, 12, 8]]
print(data.getSkyline(buildings))
